package com.wtgroup.demo.mianshi.算法.排序;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Nisus
 * @version 0.1
 * @date 2019/9/13 18:06
 */
public class RadixSort {

    public static void main(String[] args) {
        Judger.of(() -> {
            String[] nums = RandomUtil.randomArrayString((int) (Math.random() * 20 + 1), 10, 100);
            String[] copy1 = Arrays.copyOf(nums, nums.length);
            new RadixSort().sort(copy1);

            String[] copy2 = Arrays.copyOf(nums, nums.length);
            Arrays.sort(copy2);

            if (!Tools.equals(copy1, copy2)) {
                Tools.printArray(nums);
                Tools.printArray(copy1);
                Tools.printArray(copy2);
                return false;
            }
            return true;
        }).setIterCount(1000).start().print();
    }


    /**
     * ASCII码个数
     */
    private static final int BUCKET_NUM = 256;


    public static void sort(String[] arr) {

        // 初始化桶
        ArrayList<List<String>> buckets = new ArrayList<List<String>>(BUCKET_NUM);
        for (int i = 0; i < BUCKET_NUM; i++) {
            buckets.add(new ArrayList());
        }

        // 计算字符串最大长度
        int maxLen = getMaxLen(arr);
        if (maxLen == 0) {
            return;
        }

        for (int pos = maxLen - 1; pos >= 0; pos--) {
            for (int i = 0; i < arr.length; i++) {
                String s = arr[i];
                // 对于字符串, 低位"补0"; 如果要高位"补0", 需要进一步特殊处理, pos=pos-(maxLen-thisLen),
                // pos>=0, 直接用, <0, 0
                char c = 0;
                if (pos < s.length())
                    c = s.charAt(pos);
                // 定位桶
                buckets.get(c).add(s);
            }

            //  倒回源数组
            int ix = 0;
            for (List<String> bucket : buckets) {
                for (String o : bucket) {
                    arr[ix++] = o;
                }
                bucket.clear();
            }

        }
    }



    private static int getMaxLen(String[] arr) {
        int maxLen = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].length() > maxLen) {
                maxLen = arr[i].length();
            }
        }
        return maxLen;
    }

}
